package leetCode;

public class Heap {
    public static void heapSort(int [] arr){
        if(arr.length<2||arr==null){
         return;
        }
        for(int i=0;i<arr.length;i++){
            heapInsert(arr,i);
        }
        int heapSize=arr.length;
        swap(arr,0,--heapSize);
        while(heapSize>0){
            heapify(arr,0,heapSize);
            swap(arr,0,--heapSize);
        }
    }

    public static void heapInsert(int[] arr,int index){
        while(arr[index]>arr[(index-1)/2]){
            swap(arr,index,(index-1)/2);
            index=(index-1)/2;
        }
    }

    public static void heapify(int [] arr,int index,int heapSize){
        int left = index * 2 + 1;
        while (left < heapSize) {//判断是否有左孩子
            //判断是否有右孩子且右孩子是否比左孩子小，如果为true这左右之间最大为右，反之为左
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            //将之前得到的最大值与父节点比较
            largest = arr[largest] > arr[index] ? largest : index;
            //如果父节点最大，这是大根堆，不用进行操作
            if (largest == index)
                break;
            //交换索引和最大节点位置，使二叉树为大根堆
            swap(arr, index, largest);
            //将最大的孩子的索引赋给当前索引
            index = largest;
            //计算后面索引的大根堆
            left = index * 2 + 1;
        }
    }

    public static void swap(int arr[],int a,int b){
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
}
